Institut de Recherche en Informatique Fondamentale (IRIF)

CNRS

Université Paris Cité

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris Cité, et héberge une équipe-projet Inria.

Les recherches menées à l'IRIF reposent sur l’étude et la compréhension des fondements de toute l’informatique, afin d’apporter des solutions innovantes aux défis actuels et futurs des sciences numériques.

L'IRIF regroupe près de deux cents personnes. Sept de ses membres ont été lauréats de l'European Research Council (ERC), trois sont membres de l'Institut Universitaire de France (IUF), deux sont membres de l'Academia Europæa, et un est membre de l'Académie des sciences.

Suivez nous sur Mastodon, Twitter/X et LinkedIn :

LinkedIn Twitter/X Mastodon

tayssir_touili.jpg

27.3.2024
Nous accueillons une nouvelle directrice de recherche à l'IRIF, Tayssir Touili. Ses domaines d'intérêt sont la détection de logiciels malveillants, la vérification de logiciels et les méthodes formelles. Vous pouvez la rencontrer dans le bureau 4028A.

logopintofscience2024.jpg

10.4.2024
Trois projets de médiation scientifique de chercheurs à l'IRIF ont été sélectionnés pour l'édition 2024 de Pint of Science France-Paris. Le principe : découvrir une thématique ou un sujet scientifique, dans un bar. Nos chercheurs parleront protection des données, graphes et informatique quantique.

podcast_recherche_cm.jpg

19.3.2024
Après avoir été augmenté en septembre 2023, le budget alloué à l’Enseignement supérieur et à la Recherche est finalement réduit de 904 millions d’euros. Le podcast “La Science, CQFD” de France Culture s'est demandé comment se porte la recherche française et quelle direction elle prend. Claire Mathieu, directrice de recherche au CNRS à l'IRIF, intervient.

12.4.2024
La rediffusion de la conférence (en anglais) de Véronique Cortier, qui s'est tenue en février, est désormais disponible sur la chaîne YouTube de l'IRIF. Son sujet était : “Le vote électronique : conception et vérification formelle”.

mirna-dzamonja.jpeg

28.3.2024
La Société mathématique de Belgique (SMB) a décerné à Mirna Džamonja (CNRS, IRIF, Université de Paris) le “Prix Godeaux” de la SMB. “Ce prix est décerné chaque année, sur proposition d'un membre du conseil d'administration de la BMS, à un-e mathématicien-ne belge ou international-e de renom qui est invité-e à donner une conférence en Belgique”. Toutes nos félicitations !

marie-jose_iarifina.jpg

27.3.2024
Marie-Josée Iarifina a rejoint l'IRIF pour remplacer Natalia Hacquart en tant que gestionnaire financière et comptable. Venez la rencontrer et lui souhaiter la bienvenue dans le bureau 4002.

quentin_aristote.jpg

29.3.2024
Bravo à Quentin Aristote, doctorant, qui a reçu le prix Helena Rasiowa pour le meilleur papier étudiant, lors de la 32ème conférence EACSL : Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids.

dts_omer_reingold.jpg

10.4.2024
L'IRIF a le plaisir d'annoncer son deuxième Distinguished Talk de l'année ! Notre conférencier invité est Omer Reingold, professeur d'informatique à l'université de Stanford et directeur de la Simons Collaboration sur la théorie de l'Équité algorithmique (Simons Foundation). Il parlera de l'équité algorithmique. Toute personne intéressée est invitée à se joindre à nous pour cette conférence !


(Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.)

Séminaire des membres non-permanents
Jeudi 16 mai 2024, 16 heures, Salle 3052
Clément Ducros How to Achieve Secure Computation Using Coding Theory?

Secure Multiparty Computation (MPC) aims at enabling different parties to compute functions based on private inputs. Providing the parties with additional correlated and random inputs enables highly efficient MPC protocols. But how do we construct this additional correlated randomness? In this presentation, I will discuss the construction of pseudorandom correlation generators (PCG), focusing on the special case of two-party random oblivious linear evaluations (OLEs). We will explore the foundational concepts introduced by Boyle et al. (2020), examine their limitations, and demonstrate how coding theory significantly contributes to the security analysis and efficiency of the construction. This presentation is based on collaborative work with Maxime Bombar, Dung Bui, Geoffroy Couteau, Alain Couvreur, and Sacha Servan-Schreiber.

Catégories supérieures, polygraphes et homotopie
Vendredi 17 mai 2024, 14 heures, Salle 3058
Lyne Moser New methods to construct model categories

Model categories provide a good environment to do homotopy theory. A model category consists of a bicomplete category together with three classes of morphisms (weak equivalences, cofibrations, and fibrations) satisfying a list of axioms. While weak equivalences are the main players in a model category and encode how two objects should be thought of as being ``the same, the additional data of cofibrations and fibrations typically facilitates computations of homotopy limits and colimits, and of derived functors. However, because of their robust structure, model categories are usually hard to construct. In joint work with Guetta, Sarazola, and Verdugo, we develop new techniques for constructing model structures from given classes of cofibrations, fibrant objects, and weak equivalences between them. The requirement that one only needs to provide a class of weak equivalences between fibrant objects both simplifies the conditions to check and seems more natural in practice: often, the fibrant objects are the ``well-behaved objects in a model category and so the weak equivalences should only be expected to exhibit a good behavior between these objects. As a straightforward consequence of our result, we obtain a more general version of the usual right-induction theorem along an adjunction, where fibrations and weak equivalences are now only right-induced between fibrant objects; we refer to such an induced model structure as fibrantly-induced.

As applications of these new methods, we construct several model structures on the category of double categories.

Automates
Vendredi 17 mai 2024, 14 heures, Salle 3052
Laure Daviaud Weighted automata: a la carte!

I will first give a quick overview of decidability problems for weighted automata. Then, up to you! I can talk about any of the following topics, we'll vote! - decidability of the Big-O problem for max-plus automata - the many undecidability results via the halting problems of two-counter machines - learnability of weighted automata

Combinatoire énumérative et analytique
Mardi 21 mai 2024, 11 heures, Salle 3058
Jang Soo Kim (Sungkyunkwan University (SKKU)) Lecture hall graphs and the Askey scheme

We establish, for every family of orthogonal polynomials in the Askey scheme and the q-Askey scheme, a combinatorial model for mixed moments and coefficients in terms of paths on the lecture hall lattice. This generalizes to all families of orthogonal polynomials in the Askey scheme previous results of Corteel and Kim for the little q-Jacobi polynomials.

This is joint work with Sylvie Corteel, Bhargavi Jonnadula, and Jon Keating.

Algorithmes et complexité
Mardi 21 mai 2024, 15 heures, Salle 4052 (PCQC)
Xiaodi Wu (University of Maryland) Non encore annoncé.

Algorithmes et complexité
Mardi 21 mai 2024, 14 heures, Salle 3052
Lawrence Roy (Aarhus University) VOLE-in-the-Head and Post-Quantum Signatures

VOLE-in-the-head (closely related to the MPC-in-the-head paradigm of Ishai et al.) is recent technique for computationally efficient but non-succinct NIZK in the random oracle model. It was applied to post quantum signatures in the signature scheme FAEST, a submission to the NIST call for additional digital signature schemes, which works by proving knowledge of an AES key. I will present the VOLE-in-the-head technique, it's application to FAEST, and the recent “One Tree” optimizations.

One world numeration seminar
Mardi 21 mai 2024, 14 heures, Online
Gaétan Guillot (Université Paris-Saclay) Approximation of linear subspaces by rational linear subspaces

We elaborate on a problem raised by Schmidt in 1967: rational approximation of linear subspaces of $\mathbb{R}^n$. In order to study the quality approximation of irrational numbers by rational ones, one can introduce the exponent of irrationality of a number. We can then generalize this notion in the framework of vector subspaces for the approximation of a subspace by so-called rational subspaces. After briefly introducing the tools for constructing this generalization, I will present the different possible studies of this object. Finally I will explain how we can construct spaces with prescribed exponents.

Preuves, programmes et systèmes
Jeudi 23 mai 2024, 10 heures 30, ENS Lyon
Tba Séminaire CHOCOLA

Séminaire des membres non-permanents
Jeudi 23 mai 2024, 16 heures, Salle 3052
Dung Bui Non encore annoncé.

Catégories supérieures, polygraphes et homotopie
Vendredi 24 mai 2024, 10 heures 30, Salle 3052
Wojciech Dulinski (Varsovie) Eilenberg-Zilber opetopic sets and the $(\infty,0)$-model structure

In my talk, I will discuss the category $pOpe_\iota$ of positive opetopes with \iota-contractions, introduced by Zawadowski. I will then define the category $\widehat{pOpe_\iota}_{EZ}$ of Eilenberg-Zilber opetopic sets, which are presheaves on $pOpe_\iota$ analogous to simplicial sets. I will outline a modification of Cisinski theory applicable to $\widehat{pOpe_\iota}_{EZ}$, demonstrating the existence of a model structure. Additionally, I will sketch the proof of its Quillen equivalence to the Kan-Quillen model structure. If time allows, I will touch upon another model structure and its potential comparison with the Joyal model structure on simplicial sets.